#define _CRT_SECURE_NO_WARNINGS 1 
#include <vector>


class UnionFindSet
{
public:
	UnionFindSet(size_t size)
		:_set(size,-1)
	{}

	size_t FindRoot(int x)
	{
		int root = x;

		while (_set[root] >= 0)
		{
			root = _set[root];
		}
		while (_set[x] >= 0)
		{
			int parent = _set[x];
			_set[x] = root;
			x = parent;
		}

		return root;
	}

	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		if (abs(_set[root1]) < abs(_set[root2]))
		{
			std::swap(root1, root2);
		}
		if (root1 != root2)
		{
			_set[root1] += _set[root2];
			_set[root2] = root1;
		}
	}

	size_t SetCount()
	{
		size_t count = 0;
		for (auto e : _set)
		{
			if (e < 0)
				count++;
		}
		return count;
	}
	
private:
	std::vector<int> _set;
};